链接：https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=295&tqId=724&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        list<ListNode*> ls;
        for (auto e : lists)
        {
            //去除空链表
            if (e)
            ls.push_back(e);
        }

        while (ls.size() != 0 && ls.size() != 1)
        {
            list<ListNode*>::iterator first = ls.begin();
            auto second = ++ls.begin();
            //两两归并（一趟）
            while (second != ls.end())
            {
                ListNode* start = *first;
                ListNode* p1 = start->next, * p2 = *second;
                int flag = 0;//决定保留谁（first / second）
                if (start->val > (*second)->val)
                {
                    start = p2;
                    p1 = *first;
                    p2 = start->next;
                    flag = 1;
                }
                ListNode* tail = start;

                while (p1 && p2)
                {
                    if (p1->val <= p2->val)
                    {
                        tail->next = p1;
                        p1 = p1->next;
                    }
                    else
                    {
                        tail->next = p2;
                        p2 = p2->next;
                    }
                    tail = tail->next;
                }
                if (!p1) { tail->next = p2; }
                else { tail->next = p1; }
                auto prev_f = first, prev_s = second;

                //下一组
                first = ++second;
                if (second != ls.end())
                {
                    second = ++second;
                }
                //更新ls
                if (0 == flag) { ls.erase(prev_s); }
                else { ls.erase(prev_f); }
            }
        }
        return *ls.begin();
    }

};